#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
// 双指针 partition 算法
int partition1(vector<int> &nums, int left, int right) {
  int pivotIndex = right;
  int pivot = nums[right];
  while (left < right) {
    // low指针先走
    while (left < right && nums[left] < pivot)
      left++;
    while (left < right && nums[right] >= pivot)
      right--;
    if (left < right)
      swap(nums[left], nums[right]);
  }
  swap(nums[left], nums[right]);
  return left;
}
// 单指针算法
int partition2(vector<int> &nums, int left, int right) {
  int pivotIndex = right;
  int pivot = nums[right];
  // 小于pivot的区间尾指针，初始为空
  int i = left;
  for (int j = i; j < right; j++) {
    if (nums[j] < pivot) {
      swap(nums[i++], nums[j]);
    }
  }
  swap(nums[i], nums[right]);
  return i;
}

int findKthLargest(vector<int> &nums, int k) {
  int len = nums.size();
  int left = 0;
  int right = len - 1;
  int pos = len - k;
  while (left <= right) {
    int p = partition(nums, left, right);
    if (p == pos)
      break;
    if (p < pos)
      left = p + 1;
    if (p > pos)
      right = p - 1;
    cout << left << ", " << right << endl;
    for (int x : nums) {
      cout << x << ", ";
    }
    cout << endl;
  }
  return nums[pos];
}

int main() {
  vector<int> nums{3, 2, 3, 1, 2, 4, 5, 5, 6};
  int r = findKthLargest(nums, 2);
  cout << r << endl;
}